home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1994 #2 / Monster Media No. 2 (Monster Media)(1994).ISO / prog_c / tpchal_1.zip / SG.C < prev    next >
C/C++ Source or Header  |  1994-05-26  |  3KB  |  114 lines
  1. /* use all the digits 1 to 9 in a nine digit number where:
  2.     the first digit is divisible by 1,
  3.     the first two digits are divisible by 2,
  4.     ...
  5.     This program finds one solution
  6.     Answer:381654729
  7.           
  8.     by Stephan Galt (1:232/308)
  9. */
  10.  
  11. int used[10];           /* 1==used, 0==free                      */
  12. int selection_num=0;    /* the number of digits already selected */
  13. int answer[10];         /* place answers here (in locations 1-9  */
  14. double test_answer;
  15. double helper[10];
  16.  
  17. #define QUICKCHECK 1000
  18.  
  19. void build_test_answer(void)
  20. {
  21.       int x;
  22.  
  23.       test_answer=0;
  24.       for (x = 0; x < selection_num; x++)
  25.       {
  26.             test_answer += helper[selection_num - x] * answer[x + 1];
  27.       }
  28.  
  29. }
  30.  
  31.  
  32. int get_digit(void)
  33. {
  34.       int lx;
  35.  
  36.       selection_num++;
  37.  
  38.       for (lx = 1; lx < 10; lx++)
  39.       {
  40.             if (!used[lx]) /* found unused digit */
  41.             {
  42.                   used[lx]=1;
  43.                   answer[selection_num] = lx;
  44.  
  45.                   /* is answer acceptable? */
  46.                   /* build test_answer */
  47.  
  48.                   build_test_answer();
  49.  
  50.                   /* is test_answer evenly divisible by selection_num ? */
  51.  
  52.                   while (test_answer > 0)
  53.                   {
  54.                         test_answer -=QUICKCHECK * selection_num;
  55.                   }
  56.                   test_answer += QUICKCHECK * selection_num;
  57.                   while (test_answer > 0)
  58.                         test_answer -= selection_num;
  59.  
  60.                   if (test_answer == 0)
  61.                   {  /* yes */
  62.                         if(selection_num == 9)
  63.                             return(1); /* success to 9th level */
  64.                         else
  65.                         {
  66.                               if(get_digit()==1)
  67.                               {
  68.                                     /*
  69.                                     ** head back to main and display
  70.                                     ** a final answer
  71.                                     */
  72.  
  73.                                     return(1);
  74.                               }
  75.                         }
  76.                   }    /* end divisible test */
  77.  
  78.                   /* restore digit to unused */
  79.  
  80.                   used[lx]=0;
  81.             }       /* end found digit */
  82.  
  83.       }          /* end loop checking all digits at this level */
  84.       answer[selection_num] = 0; /* just pretty */
  85.       selection_num--;
  86.       return(0);     /* failed to find usuable number at this level */
  87.  
  88. }
  89. main()
  90. {
  91.       int x=9;
  92.  
  93.       helper[0]=.1;
  94.       for (x = 1; x < 10; x++)
  95.       {
  96.             used[x] = 0;
  97.             answer[x] = 0;
  98.             helper[x] = 10 * helper[x-1];
  99.       }
  100.  
  101.       x = 9;
  102.       if (0 == get_digit())
  103.             printf("\a\nNO ANSWER FOUND!!\n\a");
  104.       else
  105.       {
  106.             printf("Number = ");
  107.             while(x--)
  108.             {
  109.                   printf("%d",answer[9-x]);
  110.             }
  111.       }
  112.       exit(0);
  113. }
  114.